#include <vector>
#include <string>
#include <unordered_map>
#include <queue>
#include <unordered_set>
#include <algorithm>
using namespace std;
/*
 * @lc app=leetcode.cn id=126 lang=cpp
 *
 * [126] 单词接龙 II
 */

// @lc code=start
typedef pair<int, int> state;
class Solution {
public:
    vector<vector<string>> res;
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_map<string, int> mapper;
        for (int i = 0; i < wordList.size(); i++) mapper.insert({wordList[i], i});
        if (!mapper.count(endWord)) return res;
        if (!mapper.count(beginWord)) {
            wordList.push_back(beginWord);
            mapper.insert({beginWord, wordList.size() - 1});
        }
        unordered_map<int, int> level;
        queue<state> q; q.push({mapper[beginWord], 0}); level.insert({mapper[beginWord], 0});
        bool flag = false;
        while (!q.empty()) {
            state index = q.front(); q.pop();
            string s = wordList[index.first];
            if (s == endWord) {
                flag = true; break;
            }
            for (char & c: s) {
                char temp = c;
                for (char i = 'a'; i <= 'z'; i++) {
                    if (i == temp) continue; c = i;
                    if (mapper.count(s) && !level.count(mapper[s])) {
                        level.insert({mapper[s], index.second + 1});
                        q.push({mapper[s], index.second + 1});
                    }
                }
                c = temp;
            }
        }
        if (!flag) return res;
        vector<string> temp = {endWord};
        dfs(temp, level, 0, mapper[beginWord], wordList, beginWord, mapper);
        return res;   
    }

    void dfs(vector<string> &now, unordered_map<int, int> & level, int step, int index, vector<string> &wordList, string & endWord, unordered_map<string, int> & mapper) {
        if (wordList[index] == endWord) {
            reverse(now.begin(), now.end());
            res.push_back(now);
            reverse(now.begin(), now.end());
            return;
        }
        string s = wordList[index];
        for (char & c: s) {
            char temp = c;
            for (char i = 'a'; i <= 'z'; i++) {
                if (i == temp) continue; c = i;
                if (mapper.count(s) && level[mapper[s]] == step + 1) {
                    now.push_back(s);
                    dfs(now, level, step + 1, mapper[s], wordList, endWord, mapper);
                    now.pop_back();
                }
            }
            c = temp;
        }
    }
};
// @lc code=end

